package leetcode_100;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *Combinations_77 给定两个数字 n 和k  输出所有不重复数字的排列  该数字只有k位  所取数在1-n之间
 *describe:回溯法解决 AC 34%
 *2018年5月14日 上午9:22:13
 */
public class Combinations_77 {
	List<List<Integer>> res;
	int n;
	int k;
	public static void main(String[] args) {
		Combinations_77 test=new Combinations_77();
		test.combine(4, 2);

	}
	
	public List<List<Integer>> combine(int n, int k) {//数字最大到n k是几个数
        this.res=new ArrayList<List<Integer>>();
        this.n=n;
        this.k=k;
        help(new ArrayList<Integer>(),0);
		return this.res;
    }
	
	public void help(List<Integer> list,int top) {
		for(int i=top+1;i<=this.n;++i) {
			list.add(i);
			if(list.size()==k) {//满了
				List<Integer> now=new ArrayList<Integer>();
				now.addAll(list);
				this.res.add(now);
				}
			else
				 help(list,i);
			list.remove(list.size()-1);
		}
	}

}
